//
//  Array.cpp
//  cpp
//
//  Created by xueshan1 on 2019/10/11.
//  Copyright © 2019 xueshan1. All rights reserved.
//

#include <stdio.h>
#include <string>
#include <vector>

using namespace std;
using std :: vector;

#pragma mark - 最大和子数组
void maxSubArray_1(vector<int> array){
    int i = 0, j = 0;
    int max = 0, maxi = 0,maxj = 0;
    int sum = 0;
    
    for (i = 0; i<array.size(); i++) {
        sum = 0;
        for (j = i ; i<array.size(); j++) {
            sum += array[j];
            if (sum > max) {
                max = sum;
                maxi = i;
                maxj = j;
            }
        }
        
    }
    
}

//最优解
void maxSubArray_2(vector<int> array){
    int max = 0, maxi = 0,maxj = 0;
    int sum = array[0];
    for (int i = 1 ; i<array.size(); i++) {
        if (sum > 0) {
            sum += array[i];
            maxj = i;
        }else{
            sum = array[i];
            maxj = i-1;
        }
        
        if (sum > max) {
            max = sum;
            maxi = i;
        }
        
    }
    
}

#pragma mark  - 二分查找
//前提: 有序数组
int midFind(vector<int>array,int target){
    int begin = 0,end = array.size() - 1;
    while (begin <= end) {
        int mid = (begin + end)/2;

        if (array[mid] == target) {
            return mid;
        }else if (array[mid] > target){
            end = mid - 1;
        }else{
            begin = mid + 1;
        }
        
//        mid = (begin + end)/2;
    }
    
    return -1;
}

#pragma mark  - 二分查找 -升级版
// 排序的数组被旋转了, 找到哪一边有序, 不断改变left right,两个指针
//https://www.cnblogs.com/ariel-dreamland/p/9138064.html

#pragma mark - 将所有0移动到数组的末尾
void moveZero(vector<int>array){
    int zeroCount = 0;
    for (int i = 0; i<array.size(); i++) {
        if (array[i] == 0) {
            zeroCount++;
        }else if(zeroCount != 0){
            array[i-zeroCount] = array[i];// 记录 0 的个数, 每次移动的位置数 就是当前 0 的个数
            array[i] = 0;
        }
    }
}


#pragma mark - 第三大的数
void num3Max(vector<int>array){
    int max1 = 0, max2 = 0, max3 = 0;
    
    for (int i = 0; i<array.size(); i++) {
        if (array[i]> max1) {
            max3 = max2;
            max2 = max1;
            max1 = array[i];
        }
    }
    
}

//中等
#pragma mark -
#pragma mark - 买卖股票
//记录今天之前的最小值, 今天卖出,算利润
int maxProfit(vector<int>price){
    int min = price[0];
    int max = 0;
    for (int i = 1; i<price.size(); i++) {
        int profix = price[i] - min;
        if (profix > max) {
            max = profix;
        }
        
        if (price[i] < min) {
            min = price[i];
        }
        
    }
    return max;
}

#pragma mark - 三数之和
// a+b+c = 0, 三数之和等于, 则一定有一个为负数;(先排序,拿到第一个负数, 然后转化为求两个数的和)
//https://www.jianshu.com/p/69b0a1170f96

#pragma mark - 四数之和
//在三个数之和的基础上, 外层再加个for循环 即可
//https://blog.csdn.net/hit1110310422/article/details/80934545

#pragma mark - 跳跃游戏
// i 代表当前所在的位置, a[i] 代表从当前i位置 往后能走的最远位置
//动态规划: 新数组 dp 用于记录当前i所能到的最远位置, 不断判断下一个i所能到达的最远位置是否被上一个最远位置dp[i-1] 所覆盖, 记录较大(远)的那个
//贪心算法: 用一个变量代替 动态规划的dp数组
//https://www.cnblogs.com/libaoquan/p/7203198.html







